# 给你两个数组，arr1 和 arr2，
#  arr2 中的元素各不相同
#  arr2 中的每个元素都出现在 arr1 中
#  对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
#
#  示例：
# 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
# 输出：[2,2,2,1,4,3,3,9,6,7,19]
import collections
import sys
from typing import List


class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        i = 0
        mp = collections.defaultdict(int)
        while i < len(arr2):
            mp[arr2[i]] = i
            i += 1
        arr1.sort(key=lambda x: mp.get(x, x + sys.maxsize))
        return arr1


if __name__ == "__main__":
    arr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19]
    arr2 = [2, 1, 4, 3, 9, 6]
    arr1 = [28, 6, 22, 8, 44, 17]
    arr2 = [22, 28, 8, 6]
    res = Solution().relativeSortArray(arr1, arr2)
    print(res)

